package org.example;

import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * The type Solution.
 */
public class Solution {
    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        Logger logger = Logger.getLogger(Solution.class.getName());
        String[] tokens = {"4","13","5","/","+"};
        String result = String.valueOf(new Solution().evalRPN(tokens));
        logger.log(Level.INFO, result);
    }

    /**
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。<br>
     * 请你计算该表达式。返回一个表示表达式值的整数。<br>
     * 注意：<br>
     * 有效的算符为 '+'、'-'、'*' 和 '/' 。<br>
     * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。<br>
     * 两个整数之间的除法总是 向零截断 。<br>
     * 表达式中不含除零运算。<br>
     * 输入是一个根据逆波兰表示法表示的算术表达式。<br>
     * 答案及所有中间计算结果可以用 32 位 整数表示。<br>
     * @param tokens 字符串数组 tokens
     * @return 达式值的整数
     */
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int subtrahend = stack.pop();
                    stack.push(stack.pop() - subtrahend);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int divisor = stack.pop();
                    stack.push(stack.pop() / divisor);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }


    /**
     * 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。<br>
     * 在 Unix 风格的文件系统中规则如下：<br>
     * 一个点 '.' 表示当前目录本身。<br>
     * 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。<br>
     * 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。<br>
     * 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。<br>
     * 返回的 简化路径 必须遵循下述格式：<br>
     * 始终以斜杠 '/' 开头。<br>
     * 两个目录名之间必须只有一个斜杠 '/' 。<br>
     * 最后一个目录名（如果存在）不能 以 '/' 结尾。<br>
     * 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。<br>
     * 返回简化后得到的 规范路径 。
     * @param path path
     * @return 结果 ，String类型
     */
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        stack.push("/");
        for (String s : path.split("/")){
            if (s.equals("..") && stack.size() > 1){
                stack.pop();
                stack.pop();
            }  else if (!s.isEmpty() && !s.equals("..") && !s.equals(".")){
                stack.push(s);
                stack.push("/");
            }
        }
        while (!stack.isEmpty()){
            result.append(stack.removeLast());
        }
        if (result.length() > 1){
            result.deleteCharAt(result.length() - 1);
        }
        return result.toString();
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：
     * <p>
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     *
     * @param s s
     * @return 结果 ，boolean类型
     */
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        for (int i = 0; i < s.length(); i++){
            if (map.containsKey(s.charAt(i))){
                if (stack.isEmpty() || !map.get(s.charAt(i)).equals(stack.peek())){
                    return false;
                }
                stack.pop();
            }else {
                stack.push(s.charAt(i));
            }
        }
        return stack.isEmpty();
    }

    /**
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
     * <p>
     * 满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
     * <p>
     * 如果存在，返回 true ；否则，返回 false 。
     *
     * @param nums nums
     * @param k    k
     * @return 结果 ，boolean类型
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if (!map.containsKey(nums[i])){
                map.put(nums[i], i);
            }else {
                if (Math.abs(map.get(nums[i]) - i) <= k){
                    return true;
                }
                map.put(nums[i], i);
            }
        }
        return false;
    }

    /**
     * Gets next.
     *
     * @param n the n
     * @return the next
     */
    public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    /**
     * 编写一个算法来判断一个数 n 是不是快乐数。
     * <p>
     * 「快乐数」 定义为：
     * <p>
     * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     * <p>
     * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     * <p>
     * 如果这个过程 结果为 1，那么这个数就是快乐数。
     * <p>
     * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
     *
     * @param n n
     * @return 结果 ，boolean类型
     */
    public boolean isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
    }

    /**
     * Is anagram boolean.
     *
     * @param s the s
     * @param t the t
     * @return the boolean
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()){
            return false;
        }
        int[] chars = new int[26];
        for (int i = 0; i < s.length(); i++){
            chars[s.charAt(i) - 'a']++;
            chars[t.charAt(i) - 'a']--;
        }
        for (int i : chars){
            if (i != 0){
                return false;
            }
        }
        return true;
    }

    /**
     * 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
     * <p>
     * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
     *
     * @param pattern pattern
     * @param s       s
     * @return 结果 ，boolean类型
     */
    public boolean wordPattern(String pattern, String s) {
        char[] chars = pattern.toCharArray();
        String[] strings = s.split(" ");
        if (chars.length != strings.length){
            return false;
        }
        HashMap<Object, Integer> map = new HashMap<>();
        for (Integer i = 0; i < chars.length; i++){
            if (!Objects.equals(map.put(chars[i], i), map.put(strings[i], i))){
                return false;
            }
        }
        return true;
    }

    /**
     * 给定两个字符串 s 和 t ，判断它们是否是同构的。
     * <p>
     * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
     * <p>
     * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
     *
     * @param s s
     * @param t t
     * @return 结果 ，boolean类型
     */
    public boolean isIsomorphic(String s, String t) {
        char cs;
        char ct;
        int[] cnt1 = new int[127];
        int[] cnt2 = new int[127];
        int index = 1;
        for(int i = 0; i < s.length(); i++){
            cs = s.charAt(i);
            ct = t.charAt(i);
            if(cnt1[cs] == 0 && cnt2[ct] == 0){
                cnt1[cs] = index;
                cnt2[ct] = index;
                index++;
            }
            if(cnt1[cs] != cnt2[ct]){
                return false;
            }
        }
        return true;
    }

    /**
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     * <p>
     * 如果可以，返回 true ；否则返回 false 。
     * <p>
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     *
     * @param ransomNote ransomNote
     * @param magazine   magazine
     * @return 结果 ，boolean类型
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> map = new HashMap<>();

        if (ransomNote.length() > magazine.length()){
            return false;
        }

        for (Character m: magazine.toCharArray()){
            if (map.containsKey(m)){
                map.put(m, map.get(m) + 1);
            }else {
                map.put(m, 1);
            }
        }

        for (Character r: ransomNote.toCharArray()){
            map.computeIfPresent(r, (k, v) -> v - 1);
            if (!map.containsKey(r) || map.get(r) < 0){
                return false;
            }
        }
        return true;
    }

    /**
     * Length of longest substring int.
     *
     * @param s the s
     * @return the int
     */
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int header;
        int rightBorder = 0;
        int max = 0;
        for (header = 0; header < s.length(); header++){
            if (header != 0){
                set.remove(s.charAt(header - 1));
            }
            while (rightBorder < s.length() && !set.contains(s.charAt(rightBorder))){
                set.add(s.charAt(rightBorder));
                rightBorder++;
            }
            max = Math.max(max, set.size());
        }
        return max;
    }

    /**
     * Two sum int [ ].
     *
     * @param numbers the numbers
     * @param target  the target
     * @return the int [ ]
     */
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int[] result = new int[2];
        while (left < right){
            if (numbers[left] + numbers[right] < target){
                left++;
            }else if (numbers[left] + numbers[right] > target){
                right--;
            }else {
                result[0] = left + 1;
                result[1] = right + 1;
                break;
            }
        }
        return result;
    }
}
